package com.bondar.collections;

import java.util.Comparator;
import java.util.RandomAccess;

import com.bondar.interfaces.MyList;

public class MyCollections {

	@SuppressWarnings("rawtypes")
	public static void sort(MyList list, Comparator c) {
		if (list instanceof RandomAccess) {
			System.out.println("quick sort with comparator");
			if (list.size() == 0) {
				return;
			}
			QSort(list, 0, list.size() - 1, c);
			
		} else {
			System.out.println("bubble sort with comparator");
			sortBubble(list, c);
		}

	}

	public static void sort(MyList list) {
		if (list instanceof RandomAccess) {
			System.out.println("quick sort comparable");

			if (list.size() == 0) {
				return;
			}
			QSort(list, 0, list.size() - 1);
			
		} else {
			System.out.println("bubble sort comparable");
			sortBubble(list);
		}
	}

	/**
	 * This method sort the list
	 * 
	 * @param list
	 *            to be sorted
	 */
	@SuppressWarnings({ "unchecked", "rawtypes" })
	private static void sortBubble(MyList list) {
		for (int i = 0; i < list.size() - 1; i++) {
			for (int j = i; j < list.size(); j++) {
				if (((Comparable) list.get(i)).compareTo(list.get(j)) > 0) {
					swap(list, i, j);
				}

			}
		}
	}

	/**
	 * This method sort the list using Comparator
	 * 
	 * @param list
	 *            to be sorted
	 * @param c
	 *            Comparator
	 */
	@SuppressWarnings({ "rawtypes", "unchecked" })
	private static void sortBubble(MyList list, Comparator c) {
		for (int i = 0; i < list.size() - 1; i++) {
			for (int j = i; j < list.size(); j++) {
				if (c.compare(list.get(i), list.get(j)) > 0) {
					swap(list, i, j);
				}

			}
		}
	}

	/**
	 * This method swaps the elements at the specified positions in the<br>
	 * specified list
	 * 
	 * @param list
	 * @param i
	 * @param j
	 * @throws IndexOutOfBoundsException
	 *             if either i or j greater then list
	 */
	public static void swap(MyList list, int i, int j) {
		Object tmp = list.get(i);

		list.set(i, list.get(j));
		list.set(j, tmp);
	}

	/**
	 * This method copies all of the elements from one list into<br>
	 * another
	 * 
	 * @param dest
	 *            destination list
	 * @param src
	 *            source list
	 * @throws IndexOutOfBoundsException
	 *             if dest less than src
	 * @throws NullPointerException
	 *             if either dest or src equals null
	 */
	public static void copy(MyList dest, MyList src) {
		if (src == null || dest == null) {
			throw new NullPointerException();
		}
		
		int destSize = dest.size() - 1;

		for (int i = 0; i < src.size(); i++) {
			// is dest empty?
			if (i <= destSize) {
				dest.set(i, src.get(i));
			} else {
				dest.add(src.get(i));
			}
		}
	}

	/**
	 * This method reverses the order of the elements in the specified list
	 * 
	 * @param list
	 */
	public static void reverse(MyList list) {
		for (int i = 0; i < list.size() / 2; i++) {
			swap(list, i, list.size() - i - 1);
		}
	}

	@SuppressWarnings({ "rawtypes", "unchecked" })
	private static void QSort(MyList list, int lo, int hi, Comparator c) {
		int i = lo;
		int j = hi;

		int x = (Integer) list.get((i + j) / 2);

		while (i <= j) {
			while (c.compare(list.get(i), x) < 0 && i < hi) {
				++i;
			}
			while (c.compare(list.get(j), x) > 0 && j > lo) {
				--j;
			}

			if (i <= j) {
				swap(list, i, j);
				++i;
				--j;
			}
		}

		if (lo < j) {
			QSort(list, lo, j);
		}
		if (hi > i) {
			QSort(list, i, hi);
		}
	}

	@SuppressWarnings({ "rawtypes", "unchecked" })
	private static void QSort(MyList list, int lo, int hi) {
		int i = lo;
		int j = hi;

		int x = (Integer) list.get((i + j) / 2);

		while (i <= j) {
			while (((Comparable) list.get(i)).compareTo(x) < 0 && i < hi) {
				++i;
			}
			while (((Comparable) list.get(j)).compareTo(x) > 0 && j > lo) {
				--j;
			}
			
			if (i <= j) {
				swap(list, i, j);
				++i;
				--j;
			}
		}

		if (lo < j) {
			QSort(list, lo, j);
		}
		if (hi > i) {
			QSort(list, i, hi);
		}
	}

	/**
	 * 
	 * @param list
	 * @param key
	 * @return
	 */
	public static int binarySearch(MyList list, Object key) {
		if (list instanceof RandomAccess) {
			QSort(list, 0, list.size() - 1);
			return bSort(list, key, 0, list.size() - 1);
		} else {
			throw new IllegalArgumentException();
		}
	}

	@SuppressWarnings({ "unchecked", "rawtypes" })
	private static int bSort(MyList list, Object key, int lo, int hi) {
		int index = lo + (hi - lo) / 2;
		if (lo > hi) {
			return -(index - 1);
		}
		
		int mid = ((Comparable) list.get(index)).compareTo(key);
		if (mid > 0) {
			// left
			return bSort(list, key, 0, index - 1);
		} else if (mid < 0) {
			// right
			return bSort(list, key, index + 1, hi);
		} else {
			// found
			return index;
		}
		

	}

}
